首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1271301 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围：
要求：空间复杂度 ，时间复杂度 ，本题也有时间复杂度 的解法


输入描述:
一个正整数n


输出描述:
输出一个正整数。
示例1

输入

4

输出

3

说明

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
示例2

输入

1

输出

1
示例3

输入

2

输出

1
算法知识视频讲解
添加回答
推荐
fanhk头像 fanhk
c++动态规划版 
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

编辑于 2015-06-19 17:21:55 回复(110)
Python 3
响亮的闵玆头像 响亮的闵玆
class Solution:
    def Fibonacci(self , n: int) :
        # write code here
       
        d=[0]*n
        d[0],d[1]=1,1

        if n==1 or n==2:
            return 1
        else:
             for i in range(2,n):
                   d[i]=d[i-1]+d[i-2]
             return d[n-1]
发表于 2024-02-20 22:53:01 回复(0)
Python 3
talv头像 talv
# 搞事情
class Solution:
    def Fibonacci(self , n: int) -> int:
        import math
        a = 0.5*(1+math.sqrt(5))
        b = 0.5*(1-math.sqrt(5))
        c = (1-1/math.sqrt(5))/2
        d = c*math.pow(a,n+1)+(1-c)*math.pow(b,n+1)
        print(d)
        return(round(d))
        # write code here
发表于 2023-03-15 21:33:54 回复(0)
Python 3
JianYue头像 JianYue 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n == 1&nbs***bsp;n ==2:
            return 1
        one, two = 1, 1
        while n > 2:
            tmp = one
            one = two
            two = two + tmp
            n = n - 1
        return two

发表于 2022-09-14 11:46:30 回复(0)
Python 3
牛客659106785号头像 牛客659106785号 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        li = [0, 1, 1]
        if n>2:
            for i in range(n-2):
                num = li[-1] + li[-2]
                li.append(num)
        return li[-1]

发表于 2022-09-01 17:06:15 回复(0)
Python 3
牛客32833635号头像 牛客32833635号 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    fb = {1:1,2:1,3:2}
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n==1&nbs***bsp;n==2:
            return self.fb[n]
        else:
            if n-1 not in self.fb:self.fb[n-1] = self.Fibonacci(n-1)
            if n-2 not in self.fb:self.fb[n-2] = self.Fibonacci(n-2)
            return self.fb[n-1]+self.fb[n-2]

发表于 2022-08-23 08:02:19 回复(0)
Python 3
东方佑头像 东方佑 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<=2:
            return 1
        else:
#           递归
#             return self.Fibonacci(n-1)+self.Fibonacci(n-2)
            start=[1,1]
            for _ in range(n-2):
                start.append(start[0]+start[1])
                start.pop(0)
            return start[-1]
                

发表于 2022-07-26 15:45:07 回复(0)
Python 3
来个offer叭！头像 来个offer叭！ 
class Solution:
    def Fibonacci(self , n: int) -> int:
        fib = [0,1,1]
        for i in range(3, n+1):
            fib.append(fib[i-1]+fib[i-2])
        return fib[n]

发表于 2022-07-21 16:55:05 回复(0)
Python 3
lun__头像 lun__ 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#

class Solution:
    def Fibonacci(self , n: int) -> int:
        ## 通过递归来实现 
        # write code here
        if n == 0: 
            return 0 
        if n == 1: 
            return 1
        if n == 2: 
            return 1 
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)


class Solution:
    def Fibonacci(self, n: int) -> int:
        ## 通过动态规划来实现 
        dp = [0] * (n+1) 
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(2, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
#         print(dp) 
        return dp[n] 

发表于 2022-07-16 09:55:16 回复(0)
Python 3
秀中作乐1946头像 秀中作乐1946
递归+记忆化=动态规划
第一步：递归
递归循环 : x3=x1+x2 并且没有其他规律/pattern 则直接return self.Fibonacci(n-1) + self.Fibonacci(n-2)
同时数据起始点在x=1上，所以当x=1 返还1，注意当x=2时候会计算 Fibonacci(2-2)也就是Fibonacci(0)所以必须预设x=0时所返还的数值，则if x =0 :return 0 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n == 0: return 0
        if n == 1:
            return 1
        return self.Fibonacci(n-1)+self.Fibonacci[n-2]

第二步：记忆化
如果不记忆化，当x大于大概30，时间就爆炸了，因为计算Fibonacci(n-1)就已经重复了很多Fibonacci(n-2)
因为Fibonacci(n-1)里面会去计算Fibonacci(n-2)+Fibonacci(n-3)
    
            找到重复的代码部分想办法记录下来就可以完成记忆化

因为Fibonacci(n-2)的计算全部是重复，所以直接记忆化Fibonacci(n-2) 
class Solution:
    def __init__(self):
        self.memo=[0]   
    
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n == 0: return 0
        if n == 1:
            self.memo.append(1)
            return 1
        res =self.Fibonacci(n-1)+self.memo[n-2]
        
        self.memo.append(res)
        return res
发表于 2022-07-07 14:57:56 回复(0)
Python 3
Vivimore头像 Vivimore 
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n==2:
            return 1
        a = 1
        b = 1
        for i in range(3, n + 1):
            res = a + b
            a = b
            b = res 
        return res
发表于 2022-05-21 10:05:36 回复(0)
Python 3
燕北茶头像 燕北茶

不用递归，试试用列表直接算

class Solution:
    def __init__(self):
        self.L=[1,1]

    def Fibonacci(self , n: int) -> int:
        # write code here
        if n <=2:
            return 1
        for i in range(n-2):
            self.L.append(self.L[-1]+self.L[-2])   
        return self.L[n-1]

如果可以调矩阵，感觉用矩阵也可以

import numpy as np

class Solution:
    def __init__(self):
        self.m=np.mat('1 1;1 0')

    def Fibonacci(self , n: int) -> int:
        # write code here
        res = self.m**n
        return res[-1,0]
发表于 2022-05-06 12:12:48 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        f = [0,1,1]
        if n >= 3:
            for i in range(3, n+1):
                f.append(f[i-1]+f[i-2])
        return f[n]

发表于 2022-04-19 10:06:49 回复(0)
Python 3
ygl45头像 ygl45 
num=int(input())
num1=num2=num3=1
while num-2 > 0:
    num3=num1+num2
    num1=num2
    num2=num3
    num-=1

print(num3)
    
#孱弱的成长之路
发表于 2022-04-15 10:36:00 回复(0)
Python 3
尹煜头像 尹煜
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        fiblist = [1,1]
        i = 0 
        while i <= n-2:
            a = fiblist[i]+fiblist[i+1]
            fiblist.append(a)
            i += 1
        return fiblist[n-1]
可能不符合复杂度的要求
发表于 2022-04-13 10:08:56 回复(0)
Python 3
牛客991913212号头像 牛客991913212号
#暴力递归（会超时）
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n ==2:
            return 1
        else:
            return self.Fibonacci(n -1) + self.Fibonacci(n - 2)
       
# 采用dP动态规划   
class Solution:
    def Fibonacci(self , n: int) -> int:
        res = [0] * n
        res[0] = 1
        res[1] = 1
        for i in range(2,n):
            res[i] = res[i -1] +res[i-2]
        return res[n-1]

# 优化动态规划的空间复杂度  
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n ==2:
            return 1
        prev,curr = 1,1
        for i in range(3,n+1):
            sum = prev + curr
            prev = curr
            curr = sum
        return curr
发表于 2022-04-10 22:15:19 回复(0)
Python 3
dubim头像 dubim 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<=2:
            return 1
        x,y,z=1,1,2
        while n > 3:
            x,y = y,z
            z = x+y
            n -= 1
        return z

发表于 2022-03-23 13:33:51 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 数组 快速幂 递归
来自：寻找时间黑客在线编程大...
难度：
40条回答 205380浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号